As the technology node advances, the traditional single exposure lithography is no longer a viable technique. At the 20 nm node, semiconductor manufacturers have adopted double patterning lithography techniques. Double patterning lithography decomposes a layout design into two portions for two masks (sometimes referred to as two colored portions), of which each is patterned with the existing 193 nm water immersion lithography. Not all existing layout designs, however, can be readily shrunk to the 20 nm node using double patterning lithography. This is because some parts of a layout design may not be decomposed into two colored portions that can maintain the double patterning compliance—the minimum space between layout features of the same color is two times that between layout features of different colors. Particularly challenging are two-dimensional layout features such as line-ends and via features.
In addition to difficulties in handling two-dimensional features, double patterning lithography may not be adequate even for one-dimensional layout features at the 14 nm node and below. While extreme ultra-violet (EUV) lithography and self-aligned double patterning are two possible options, the former is still not yet ready for manufacturing due to issues related to throughput, mask reflectivity and resist performance and the latter may restrict layout designs too much. As such, the triple patterning lithography appears to be a promising solution for handling designs for the 14 nm node and below. Even the quadruple patterning lithography has already been under development.
Triple patterning lithography typically employs a flow known as litho-etch-litho-etch-litho-etch (LELELE), a natural extension of double patterning lithography. The final substrate pattern is the logical OR of three successive lithography+etch sequences. By using the triple patterning lithography, further feature-size scaling can be achieved by reducing line-end-to-line spacing. Moreover, some layout features that do not have a conflict-free solution for double patterning lithography can be decomposed into three masks. Yet this does not mean layout decomposition is easier for the triple patterning lithography. In some sense, it is more difficult.
Layout decomposition for the double patterning lithography can be treated as a two-coloring problem in graph theory. The two-coloring problem is known to be computable in polynomial time. Layout decomposition for other multiple patterning lithography techniques, on the other hand, is essentially a multiple-coloring (other than two-coloring) problem and not solvable in polynomial time—an NP-complete problem. The solution time for such a problem increases exponentially with the number of nodes in the coloring graph. Therefore, rigorous full layout design decomposition algorithms such as the brute force method that tries all options are not practical. A simpler method for the triple patterning lithography, called the poor man's triple patterning method, reuses a two-coloring method and attempts to remove double patterning conflicts by adding the third color. This has the advantage of providing a good run time but does not provide good color balance or guarantee finding compliant solutions, for very dense layers like metal 1, even if they exist. Methods based on integer linear programming have been reported, which attempt to minimize the conflict number and/or the stitch number. These methods are also NP-complete and have poor scalability. Even with the reported acceleration techniques, turn-around time/memory performance still needs improvement. Challenges thus remain in developing effective layout decomposition techniques for the triple and more patterning lithography.